package interviewclassic;


/**
 * @author ZhanBo
 * @date 2020/8/4
 */
public class Solution0207 {

    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        ListNode headB = new ListNode(5);
        ListNode nodeA1 = new ListNode(1);

        headA.next = nodeA1;


        ListNode nodeB1 = new ListNode(1);
        ListNode nodeB0 = new ListNode(0);
        headB.next = nodeB0;
        nodeB0.next = nodeB1;


        ListNode node8 = new ListNode(8);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node8.next = node4;
        node4.next =node5;

        nodeA1.next =node8;
        nodeB1.next =node8;

        System.out.println(getIntersectionNode(headA, headB));
    }

    /**
     * 面试题 02.07. 链表相交
     * 给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。
     * 换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
     *
     * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
     * 输出：Reference of the node with value = 8
     * 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode result = null;
        boolean isOK = false;
        ListNode tempB;
        while (headA!=null && !isOK){
            tempB = headB;
            while (tempB!=null){
                if (headA == tempB){
                    result =headA;
                    isOK = true;
                    break;
                }
                tempB = tempB.next;
            }
            headA = headA.next;
        }
        return result;
    }


    /**
     * 设链表A的长度为a，链表B的长度为b，A到相交结点的距离为c,B到相交节点的距离为d，显然可以得到两者相交链表的长度：a - c = b - d，
     * 变换一下式子得到:a + d = b + c
     * 我们用一个指针从链表A出发，到末尾后就从B出发，用另一个指针从B出发，到末尾后从A出发，由于上面的公式，
     * 当前一个指针走了a+d步数时，后一个指针走了b+c,两步数相等，即走到了相交节点。
     *
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode t1 = headA;
        ListNode t2 = headB;
        while(t1 != t2){
            t1 = t1 != null ? t1.next : headB;
            t2 = t2 != null ? t2.next : headA;
        }
        return t2;
    }

}
